package edu.whu.rose.clock.kps.algorithm.blinks2.search3;

import java.io.FileWriter;
import java.io.IOException;
import java.io.UnsupportedEncodingException;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import com.sleepycat.je.DatabaseException;

import edu.whu.rose.clock.kps.algorithm.blinks.index.BlockKeyword;
import edu.whu.rose.clock.kps.algorithm.blinks.index.BlockVertexKeyword;
import edu.whu.rose.clock.kps.algorithm.blinks2.index.BilevelIndexDB2;
import edu.whu.rose.clock.kps.algorithm.blinks2.index.KNEntry2;
import edu.whu.rose.clock.kps.algorithm.blinks2.index.NKEntry2;
import edu.whu.rose.clock.kps.algorithm.blinks2.index.PNEntry2;
import edu.whu.rose.clock.kps.datastruct.SimpleAnswer;
import edu.whu.rose.clock.kps.datastruct.SimpleSubgraphVertex;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.MyMath;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;

public class BiLevelSearch31 {

	private BilevelIndexDB2 bidb;
	
	private short bound;
	
	public long firstkTime;
	public long topkTime;
	public long indexTime;
	
	private String[] keywords;
	
	private HashMap<BlockKeyword, KNEntry2[]> knentries;
	private HashMap<SimpleSubgraphVertex, PNEntry2[]> pnentries;
	
	private HashMap<Integer, PotentialTree31> trees;
	private HashMap<Integer, int[]> allPredecessors;
	
	private FileWriter fw;
	
	public boolean needPrint;
	
	public BiLevelSearch31(BilevelIndexDB2 bidb, FileWriter fw) {
		this.bidb = bidb;
		this.fw = fw;
	}
	
	public static void main(String[] args) {
		BilevelIndexDB2 bidb = new BilevelIndexDB2();
		if (bidb.initEnv() && bidb.openDB()) {

			FileWriter fw = null;
			try {
				fw = new FileWriter("C:/Users/clock/Desktop/Experiments/blinks [].txt");
			}
			catch (IOException ex) {
				ex.printStackTrace();
			}
			
			BiLevelSearch31 blinks = new BiLevelSearch31(bidb, fw);
			
//			String[] keywords = new String[]{"self-organizing", "p2p"};
//			String[] keywords = new String[]{"eric", "alien"};
//			String[] keywords = new String[]{"schema", "reuse"};
//			String[] keywords = new String[]{"object-oriented", "metadata", "oois"};
//			String[] keywords = new String[]{"adam", "protein", "structure"};
//			String[] keywords = new String[]{"database", "supervised", "learning"};
//			String[] keywords = new String[]{"object-oriented", "3d", "graphics"};
//			String[] keywords = new String[]{"ieee", "conference", "peer-to-peer", "self-organizing"};
//			String[] keywords = new String[]{"information", "visualization", "james", "edward"};
//			String[] keywords = new String[]{"adaptive", "scheduling", "grid", "steven"};
			String[] keywords = new String[]{"paul", "image", "content", "retrieval", "video"};
			
			int[] k = new int[]{10, 25, 50};
			int z = 1;

			long[] totalFirstkTimes = new long[k.length];
			long[] totalTopkTimes = new long[k.length];
			try {
				for (int v = 0; v < k.length; v++) {
					blinks.needPrint = true;
					for (int w = 0; w < z; w++) {
						SimpleAnswer[] answers = blinks.process(keywords, k[v]);
						if (answers != null) {
							if (blinks.needPrint) {
								fw.write("top-k answers:\r\n");
								double sum = 0.0d;
								int i = 0;
								for (; i < answers.length; i++) {
									SimpleAnswer sa = answers[i];
									fw.write("Rank " + (i + 1) + ": {" + sa.getScore() + "} ");
									fw.write(" root[" + sa.getRoot() + "] ");
									sum += sa.getScore();
									for (int y = 0; y < sa.getLeafNumber(); y++) {
										int[] path = sa.getPath(y);
										fw.write("( ");
										if (path != null) {
											for (int m = 0; m < path.length; m++) {
												fw.write(path[m] + ", ");
											}
										}
										fw.write(" )");
									}
									fw.write("\r\n");
									fw.write("\r\n");
								}
								if (i == 0) {
									fw.write("Sorry, no result is found.\r\n");
								}
								else {
									fw.write("Average score: " + (sum / Math.min(k[v], i)) + "\r\n");
								}
							}

							fw.write("Time exhausted for searching first-k answers: " + blinks.firstkTime + "ms\r\n");
							fw.write("Time exhausted for reading index: " + blinks.indexTime + "ms\r\n");
							fw.write("Time exhausted for searching top-k answers: " + blinks.topkTime + " ms\r\n");
							
							totalFirstkTimes[v] += blinks.firstkTime;
							totalTopkTimes[v] += blinks.topkTime;
						}
						else {
							System.out.println("Sorry, no result is found.");
						}
						System.out.println("repeated " + (w + 1) + " times");
						blinks.needPrint = false;
					}
					System.out.println("top-" + k[v] + " finished");
					fw.write("\r\n");
					fw.write("\r\n");
					fw.write("\r\n");
					fw.write("\r\n");
					fw.write("\r\n");
				}
			
				fw.write("\r\n");
				fw.write("\r\n");
				fw.write("\r\n");
				fw.write("\r\n");
				fw.write("\r\n");
				for (int v = 0; v < k.length; v++) {
					fw.write("Average time exhausted for searching first-" + k[v] +" answers: " + 
							((double)totalFirstkTimes[v] / z) + "ms\r\n");
					fw.write("Average time exhausted for searching top-" + k[v] +" answers: " + 
							((double)totalTopkTimes[v] / z) + "ms\r\n");
					fw.write("\r\n");
				}
				
				
				fw.close();
			}
			catch (IOException ex) {
				ex.printStackTrace();
			}
			
			bidb.closeDB();
		}
	}
	
	public SimpleAnswer[] process(String[] keywords, int k) {
		Date startTime = new Date();
		
		this.keywords = keywords;
		
		SimpleAnswer[] topk = new SimpleAnswer[k];
		int size = 0;
		
		firstkTime = 0;
		topkTime = 0;
		indexTime = 0;
		
		knentries = new HashMap<BlockKeyword, KNEntry2[]>();
		pnentries = new HashMap<SimpleSubgraphVertex, PNEntry2[]>();
		
		trees = new HashMap<Integer, PotentialTree31>();
		allPredecessors = new HashMap<Integer, int[]>();

		GroupHeap31[] heaps = new GroupHeap31[keywords.length];
		
		ArrayList<HashSet<Integer>> crossed = new ArrayList<HashSet<Integer>>();
		for (int i = 0; i < keywords.length; i++) {
			crossed.add(new HashSet<Integer>());
		}
		
		HashSet<Integer> abandoned = new HashSet<Integer>();
		
		int visitTime = 0;
		int repeatTime = 0;
		
		bound = Short.MAX_VALUE;
		boolean overBound = false;
		
		boolean first_k = true;
		
		Date date = null;
		
		// initialize heaps
		for (int i = 0; i < keywords.length; i++) {
			heaps[i] = new GroupHeap31();
			date = new Date();
			int[] blockIds = null;
			try {
				blockIds = bidb.getFromKeywordBlock(keywords[i]);
			}
			catch (DatabaseException ex) {
				ex.printStackTrace();
			}
			catch (UnsupportedEncodingException ex) {
				ex.printStackTrace();
			}
			indexTime += new Date().getTime() - date.getTime();
			for (int j = 0; j < blockIds.length; j++) {
				BlockKeyword bk = new BlockKeyword(blockIds[j], keywords[i]);
				KNEntry2[] list = null;
				date = new Date();
				try {
					list = bidb.getFromKeywordVertex(bk);
					if (list == null) {
						System.err.println("Error: cannot find KN list for block #" + 
								blockIds[j] + " and keyword: " + keywords[i]);
						System.exit(1);
					}
				}
				catch (DatabaseException ex) {
					ex.printStackTrace();
				}
				indexTime += new Date().getTime() - date.getTime();
				KNCursor31 knc = new KNCursor31(blockIds[j], list);
				knentries.put(bk, list);
				heaps[i].enqueue(knc);
			}
		}
		
		try {
			while (true) {
				// expand group by group
				for (int i = 0; i < keywords.length; i++) {
					visitTime++;
					
					Cursor31 cursor = heaps[i].dequeue();
					cursor.next();

					int block = cursor.getBlock();
					short distance = cursor.getDistance();
					int vertex = cursor.getNode();
					int first = cursor.getFirst();
					
					Integer Root = new Integer(vertex);
					
					// put the cursor back to heap if it is not empty
					if (!cursor.empty()) {
						heaps[i].enqueue(cursor);
					}

					if (vertex == 116133 && i == 3) {
						System.out.println();
					}

					// maintaining predecessor records, which is always necessary
					int[] predecessors = allPredecessors.get(Root);
					if (predecessors == null) {
						predecessors = new int[keywords.length];
						predecessors[i] = first;
						allPredecessors.put(Root, predecessors);
					}
					else {
						if (predecessors[i] == 0) {
							predecessors[i] = first;
						}
						else {
							repeatTime++;
						}
					}

					// do not visit this root if it has been abandoned
					if (abandoned.contains(Root)) {
						continue;
					}
					
					// visit current root
					boolean mark = true;
					PotentialTree31 tree = trees.get(Root);

					// the tree does not exist
					// produce a new tree at this root, and try forward connection to other group in this block
					if (tree == null) {
						tree = new PotentialTree31(keywords.length);
						tree.setDistance(i, distance);
						// try to look forward
						date = new Date();
						short np = bidb.getFromVertexPortal(new SimpleSubgraphVertex(block, vertex));
						indexTime += new Date().getTime() - date.getTime();
						for (int j = 0; j < keywords.length; j++) {
							if (j != i) {
								short nk = (short)0;
								NKEntry2 nke = null;
								try {
									date = new Date();
									nke = bidb.getFromVertexKeyword(new BlockVertexKeyword(block, vertex, keywords[j]));
									indexTime += new Date().getTime() - date.getTime();
									if (nke != null) {
										nk = nke.getDistance();
										if (np >= nk) { // the shortest path from root to keywords[j] is found
											tree.setDistance(j, nk);
											predecessors[j] = nke.getFirst();
											tree.setOriginBlock(block);
										}
										else {
											tree.setD2(j, np);
										}
									}
									else {
										tree.setD2(j, np);
									}
								}
								catch (DatabaseException ex) {
									ex.printStackTrace();
								}
							}
						}
						
						trees.put(Root, tree); // put the tree into the forest
					}
					// the tree exists, but is over large and so will be abandoned
					else if (bound < Short.MAX_VALUE && sumLBD(tree, heaps, block, keywords) > bound) {
						// abandon the tree
						abandoned.add(Root);
						trees.remove(Root);
						mark = false;
					}
					// the tree exists and is not over large, and has not been visited by this group
					else if (tree.getDistance(i) == Short.MAX_VALUE) {
						// update the shortest path from this root to keywords[i]
						tree.setDistance(i, distance);
					}
					// the tree exists and is not over large, but has been visited by this group
					else {
						// do nothing
						mark = false;
					}

					if (mark) { // the tree has been inserted or modified
						if (tree.isAnswer()) { // the tree is a new answer
							if (size < k || tree.sumDistances() < topk[k - 1].getScore()) {
								
//								if (vertex == 113607) {
//									System.out.println();
//								}
								
								SimpleAnswer newAnswer = convert(vertex, tree); // convert the tree to answer
								size = addTopKAnswer(newAnswer, topk, size); // add the answer to top-k
							}
							
							// abandon the tree, since we only allow single tree rooted at this vertex
							abandoned.add(Root);
							trees.remove(Root);

							if (size == k) {
								if (first_k) { // this is the first time we have k answers
									try {
										Date firstk = new Date();
//										System.out.println("Time exhausted for reading index: " + indexTime + "ms");
										firstkTime = firstk.getTime() - startTime.getTime() - indexTime;
										if (needPrint) {
											fw.write("first-k answers:\r\n");
											short sum = (short)0;
											for (int n = 0; n < topk.length; n++) {
												SimpleAnswer sa = topk[n];
												fw.write("Rank " + (n + 1) + ": {" + sa.getScore() + "} ");
												fw.write(" root[" + sa.getRoot() + "] ");
												sum += sa.getScore();
												for (int y = 0; y < sa.getLeafNumber(); y++) {
													int[] path = sa.getPath(y);
													fw.write("( ");
													if (path != null) {
														for (int m = 0; m < path.length; m++) {
															fw.write(path[m] + ", ");
														}
													}
													fw.write(" )");
												}
												fw.write("\r\n");
												fw.write("\r\n");
											}
											fw.write("Average score: " + ((double)sum / k) + "\r\n");
										}
									}
									catch (IOException ex) {
										ex.printStackTrace();
									}
									first_k = false;
								}
								bound = (short)topk[k - 1].getScore();
							}
						}
					}
					
					// process for crossing blocks
					if (!crossed.get(i).contains(Root)) { // this root has not been crossed as a portal
						date = new Date();
						int[] PBList = bidb.getFromPortalBlock(vertex);
						indexTime += new Date().getTime() - date.getTime();
						if (PBList != null) { // this root is indeed a portal
							crossed.get(i).add(Root); // mark that it is crossed
							if (distance != (short)0) { // if this root is not a matched vertex
								for (int j = 0; j < PBList.length; j++) { // for each block this portal connects
									int ablock = PBList[j];
									if (ablock != block) { // if the block is not current block
										SimpleSubgraphVertex bk = new SimpleSubgraphVertex(ablock, vertex);
										PNEntry2[] list = pnentries.get(bk);
										if (list == null) {
											date = new Date();
											try {
												list = bidb.getFromPortalVertex(bk);
												if (list == null) {
													System.err.println("Error: cannot find PN list for block #" + 
															block + " and portal #" + vertex);
													System.exit(1);
												}
											}
											catch (DatabaseException ex) {
												ex.printStackTrace();
											}
											indexTime += new Date().getTime() - date.getTime();
											pnentries.put(bk, list);
										}
										PNCursor31 pnc = new PNCursor31(ablock, vertex, distance, list);
										if (!pnc.empty()) {
											heaps[i].enqueue(pnc); // add a new PN cursor
										}
									}
								}
							}
						}
					}
					
					// check if algorithm can be stopped
					if (size < k) {
						continue;
					}
					
					// condition 1: trees rooted at never-visited vertexes are all larger than the bound
					if (!overBound) {
						short total = (short)0;
						for (int j = 0; j < keywords.length; j++) {
							short top = heaps[j].top();
							if (top != Short.MAX_VALUE) {
								total += top;
							}
						}
						if (total > bound) {
							overBound = true;
						}
					}
					
					if (overBound) {
						// condition 2: trees rooted at already-visited vertexes have 
						// lower bounds larger than the bound
						Iterator<Integer> it = trees.keySet().iterator();
						while (it.hasNext()) {
							Integer root = it.next();
//							if (root.intValue() == 116133) {
//								System.out.println();
//							}
							PotentialTree31 pt = trees.get(root);
							if (sumLBD(pt, heaps, block, keywords) <= bound) {
//								break;
							}
							else {
								abandoned.add(root);
								it.remove();
							}
						}
						if (trees.size() > 0) {
							continue;
						}
	
						// stopping the algorithm
						Date endTime = new Date();
						topkTime = endTime.getTime() - startTime.getTime() - indexTime;
						
						return topk;
					}
				}
			}
		}
		catch (DatabaseException ex) {
			ex.printStackTrace();
		}
		
		// finish all
		Date endTime = new Date();
		topkTime = endTime.getTime() - startTime.getTime() - indexTime;
		
		return topk;
	}
	
	private SimpleAnswer convert(int root, PotentialTree31 pt) {
//		if (root == 173882) {
//			System.out.println();
//		}
		
		int[] leaves = new int[pt.size()];
		int[][] paths = new int[pt.size()][];
		SequentialIntArray allVertexes = new SequentialIntArray();
		allVertexes.insert(root);
		
		for (int i = 0; i < pt.size(); i++) {
			paths[i] = getPath(i, root, pt, allVertexes);
			if (paths[i] == null) {
				leaves[i] = root;
			}
			else {
				leaves[i] = paths[i][paths[i].length - 1];
			}
		}
		
		return new SimpleAnswer(root, leaves, paths, allVertexes.getArray());
	}
	
	private int[] getPath(int i, int root, PotentialTree31 pt,
			SequentialIntArray allVertexes) {
		ExpandableIntArray eia = new ExpandableIntArray();
		int current = root;

//		if (current == 13884 && i == 0) {
//			System.out.println();
//		}
		
		
		while (current != -1) {
			int first = 0;
			int [] predecessors = allPredecessors.get(current);
			if (predecessors == null) {
				break;
			}
			first = predecessors[i];

//			if (first == 115426 && i == 0) {
//				System.out.println();
//			}
			
			if (first == 0) {
				break;
			}
			else if (first != -1) {
				allVertexes.insert(first);
				eia.add(first);
				current = first;
			}
			else {
				return eia.toArray();
			}
		}

		int block = pt.getOriginBlock();
		
		KNEntry2[] list = knentries.get(new BlockKeyword(block, keywords[i]));
//		if (list == null) {
//			System.out.println();
//		}
		for (int j = list.length - 1; j >= 0; j--) {
			if (list[j].getNode() == current) {
				current = list[j].getFirst();
				
				if (current == -1) {
					return eia.toArray();
				}
				else {
					eia.add(current);
					allVertexes.insert(current);
				}
			}
		}
		
		System.err.println("Error: path from " + current + " to group " + i + " not found");
		
		return eia.toArray();
	}
	
	private short sumLBD(PotentialTree31 tree, GroupHeap31[] heaps, int block, String[] keywords) {
		short sum = (short)0;
		for (int i = 0; i < tree.size(); i++) {
			short distance = tree.getDistance(i);
			if (distance < Short.MAX_VALUE) {
				sum += distance;
			}
			else {
				short d1 = (short)0;
				if (!heaps[i].isEmpty()) {
					d1 = heaps[i].top();
				}
				else {
					return Short.MAX_VALUE;
				}
				short d2 = tree.getD2(i);
				if (d2 == Short.MAX_VALUE) {
					return Short.MAX_VALUE;
				}
				short d = (short)Math.max(d1, d2);
				sum += d;
			}
		}
		return sum;
	}

	private int addTopKAnswer(SimpleAnswer answer, SimpleAnswer[] topk, int size) {
		int pos = -1;
		boolean inserted = false;
		for (int i = 0; i < size; i++) {
			int x = answer.compare(topk[i]);
			if (x == MyMath.ARR1_CONTAIN_ARR2) {
				return size;
			}
			else if (x == MyMath.ARR2_CONTAIN_ARR1) {
				if (!inserted) {
					for (int j = i; j > pos + 1; j--) {
						topk[j] = topk[j - 1];
					}
					topk[pos + 1] = answer;
					inserted = true;
				}
				else {
					for (int j = i; j < size - 1; j++) {
						topk[j] = topk[j + 1];
					}
					size--;
				}
			}
			else if (x == MyMath.ARR1_EQUAL_ARR2) {
				if (answer.getScore() < topk[i].getScore()) {
					for (int j = i; j > pos + 1; j--) {
						topk[j] = topk[j - 1];
					}
					topk[pos + 1] = answer;
					return size;
				}
				else {
					return size;
				}
			}
			
			if (answer.getScore() >= topk[i].getScore()) {
				pos = i;
			}
		}
		
		if (inserted) {
			return size;
		}
		
		if (pos < size - 1) {
			if (size < topk.length) {
				for (int i = size; i > pos + 1; i--) {
					topk[i] = topk[i - 1];
				}
				size++;
			}
			else {
				for (int i = topk.length - 1; i > pos + 1; i--) {
					topk[i] = topk[i - 1];
				}
			}
			topk[pos + 1] = answer;
		}
		else if (size < topk.length) {
			topk[size] = answer;
			size++;
		}
		
		return size;
	}

}
